package com.hardy.backtracking;

/**
 * n皇后问题
 * User: Ruijie Date: 2016/9/23
 */
public class QueenProblem {
    public static int count=0;
    public static int totalNQueens(int n){
        int[] A=new int[n+1];
        int[] res=new int[1];
        dfs(1,A,res);
        return res[0];
    }

    private static void dfs(int n, int[] A,int[] res) {
        if(n>=A.length){
            res[0]++;
        }else{
            for(int j=1;j<A.length;j++){
                if(check(A,n,j)){
                    A[n]=j;
                    dfs(n+1,A,res);
                }
                A[n]=0;
            }
        }
    }

    private static boolean check(int[] a, int n, int j) {
        for(int i=1;i<n;i++){
            if(j==a[i]||Math.abs(n-i)==Math.abs(j-a[i])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(totalNQueens(13));
    }
}
